package com.gitee.wsl.time.wheel

import com.gitee.wsl.data.cache.listener.RemovalCause
import com.gitee.wsl.mathematics.function.frequency.ceilingPowerOfTwo
import kotlin.math.max
import kotlin.math.min
import kotlin.time.Duration.Companion.days
import kotlin.time.Duration.Companion.hours
import kotlin.time.Duration.Companion.minutes
import kotlin.time.Duration.Companion.seconds

/**
 * A hierarchical timer wheel to add, remove, and fire expiration events in amortized O(1) time. The
 * expiration events are deferred until the timer is advanced, which is performed as part of the
 * cache's maintenance cycle.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 */
class TimerWheel<K, V> : Iterable<Node<K, V>> {
    val wheel = Array<Array<Node<K, V>>>(BUCKETS.size){ i->
        Array(BUCKETS[i]){j->
            Sentinel<K, V>()
        }
    }

    var nanos: Long = 0

//    init {
//        for (i in wheel.indices) {
//            wheel[i] = Array(BUCKETS[i]){j->
//                
//            }
//            for (j in wheel[i].indices) {
//                wheel[i][j] = Sentinel<Any?, Any?>()
//            }
//        }
//    }

    /**
     * Advances the timer and evicts entries that have expired.
     *
     * @param cache the instance that the entries belong to
     * @param currentTimeNanos the current time, in nanoseconds
     */
    fun advance(cache: BoundedAble<K, V>, currentTimeNanos: Long) {
        var currentTimeNanos = currentTimeNanos
         var previousTimeNanos = nanos
        nanos = currentTimeNanos

        // If wrapping then temporarily shift the clock for a positive comparison. We assume that the
        // advancements never exceed a total running time of Long.MAX_VALUE nanoseconds (292 years)
        // so that an overflow only occurs due to using an arbitrary origin time (System.nanoTime()).
        if ((previousTimeNanos < 0) && (currentTimeNanos > 0)) {
            previousTimeNanos += Long.Companion.MAX_VALUE
            currentTimeNanos += Long.Companion.MAX_VALUE
        }

        try {
            for (i in SHIFT.indices) {
                val previousTicks = (previousTimeNanos ushr SHIFT[i].toInt())
                val currentTicks = (currentTimeNanos ushr SHIFT[i].toInt())
                val delta = (currentTicks - previousTicks)
                if (delta <= 0L) {
                    break
                }
                expire(cache, i, previousTicks, delta)
            }
        } catch (t: Throwable) {
            nanos = previousTimeNanos
            throw t
        }
    }

    /**
     * Expires entries or reschedules into the proper bucket if still active.
     *
     * @param cache the instance that the entries belong to
     * @param index the timing wheel being operated on
     * @param previousTicks the previous number of ticks
     * @param delta the number of additional ticks
     */
    fun expire(cache: BoundedAble<K, V>, index: Int, previousTicks: Long, delta: Long) {
        val timerWheel: Array<Node<K, V>> = wheel[index]
        val mask = timerWheel.size - 1

        // We assume that the delta does not overflow an integer and cause negative steps. This can
        // occur only if the advancement exceeds 2^61 nanoseconds (73 years).
        val steps = min(1 + delta.toInt(), timerWheel.size)
        val start = (previousTicks and mask.toLong()).toInt()
        val end = start + steps

        for (i in start..<end) {
            val sentinel: Node<K, V> = timerWheel[i and mask]
            val prev = sentinel.previousInWriteOrder
            var node = sentinel.nextInWriteOrder
            sentinel.previousInWriteOrder = sentinel
            sentinel.nextInWriteOrder = sentinel

            while (node != sentinel) {
                val next = node!!.nextInWriteOrder
                node.previousInWriteOrder = null
                node.nextInWriteOrder = null

                try {
                    if (((node.variableTime - nanos) > 0) || !cache.evictEntry(node, RemovalCause.EXPIRED, nanos)
                    ) {
                        schedule(node)
                    }
                    node = next
                } catch (t: Throwable) {
                    node!!.previousInWriteOrder = sentinel.previousInWriteOrder
                    node.nextInWriteOrder = next
                    sentinel.previousInWriteOrder!!.nextInWriteOrder = node
                    sentinel.previousInWriteOrder = prev
                    throw t
                }
            }
        }
    }

    /**
     * Schedules a timer event for the node.
     *
     * @param node the entry in the cache
     */
    fun schedule(node: Node<K, V>) {
        val sentinel: Node<K, V> = findBucket(node.variableTime)
        link(sentinel, node)
    }

    /**
     * Reschedules an active timer event for the node.
     *
     * @param node the entry in the cache
     */
    fun reschedule(node: Node<K, V>) {
        if (node.nextInWriteOrder != null) {
            unlink(node)
            schedule(node)
        }
    }

    /**
     * Removes a timer event for this entry if present.
     *
     * @param node the entry in the cache
     */
    fun deschedule(node: Node<K, V>) {
        unlink(node)
        node.nextInWriteOrder = null
        node.previousInWriteOrder = null
    }

    /**
     * Determines the bucket that the timer event should be added to.
     *
     * @param time the time when the event fires
     * @return the sentinel at the head of the bucket
     */
    fun findBucket( time: Long): Node<K, V> {
        var time = time
        val duration = max(0L, time - nanos)
        if (duration == 0L) {
            time = nanos
        }

        val length = wheel.size - 1
        for (i in 0..<length) {
            if (duration < SPANS[i + 1]) {
                val ticks = (time ushr SHIFT[i].toInt())
                val index = (ticks and (wheel[i].size - 1).toLong()).toInt()
                return wheel[i][index]
            }
        }
        return wheel[length][0]
    }

    /** Adds the entry at the tail of the bucket's list.  */
    fun link(sentinel: Node<K, V>, node: Node<K, V>) {
        node.previousInWriteOrder = sentinel.previousInWriteOrder
        node.nextInWriteOrder = sentinel

        sentinel.previousInWriteOrder?.nextInWriteOrder = node
        sentinel.previousInWriteOrder = node
    }

    /** Removes the entry from its bucket, if scheduled.  */
    fun unlink(node: Node<K, V>) {
        val next: Node<K, V>? = node.nextInWriteOrder
        if (next != null) {
            val prev = node.previousInWriteOrder
            next.previousInWriteOrder = prev
            prev?.nextInWriteOrder = next
        }
    }

    val expirationDelay: Long
        /** Returns the duration until the next bucket expires, or [Long.MAX_VALUE] if none.  */
        get() {
            for (i in SHIFT.indices) {
                val timerWheel: Array<Node<K, V>> = wheel[i]
                val ticks = (nanos ushr SHIFT[i].toInt())

                val spanMask = SPANS[i] - 1
                val start = (ticks and spanMask).toInt()
                val end = start + timerWheel.size
                val mask = timerWheel.size - 1
                for (j in start..<end) {
                    val sentinel: Node<K, V> = timerWheel[(j and mask)]
                    val next: Node<K, V>? = sentinel.nextInWriteOrder
                    if (next === sentinel) {
                        continue
                    }
                    val buckets = (j - start).toLong()
                     var delay = (buckets shl SHIFT[i].toInt()) - (nanos and spanMask)
                    delay = if (delay > 0) delay else SPANS[i]

                    for (k in i + 1..<SHIFT.size) {
                        val nextDelay = peekAhead(k)
                        delay = min(delay, nextDelay)
                    }

                    return delay
                }
            }
            return Long.Companion.MAX_VALUE
        }

    /**
     * Returns the duration when the wheel's next bucket expires, or [Long.MAX_VALUE] if empty.
     *
     * @param index the timing wheel being operated on
     */
    fun peekAhead(index: Int): Long {
        val ticks = (nanos ushr SHIFT[index].toInt())
        val timerWheel: Array<Node<K, V>> = wheel[index]

        val spanMask = SPANS[index] - 1
        val mask = timerWheel.size - 1
        val probe = ((ticks + 1) and mask.toLong()).toInt()
        val sentinel: Node<K, V> = timerWheel[probe]
        val next: Node<K, V>? = sentinel.nextInWriteOrder
        return if (next == sentinel) Long.Companion.MAX_VALUE else (SPANS[index] - (nanos and spanMask))
    }

    /**
     * Returns an iterator roughly ordered by the expiration time from the entries most likely to
     * expire (oldest) to the entries least likely to expire (youngest). The wheels are evaluated in
     * order, but the timers that fall within the bucket's range are not sorted.
     */
    override fun iterator(): Iterator<Node<K, V>> {
        return AscendingIterator()
    }

    /**
     * Returns an iterator roughly ordered by the expiration time from the entries least likely to
     * expire (youngest) to the entries most likely to expire (oldest). The wheels are evaluated in
     * order, but the timers that fall within the bucket's range are not sorted.
     */
    fun descendingIterator(): Iterator<Node<K, V>> {
        return DescendingIterator()
    }

    /** An iterator with rough ordering that can be specialized for either direction.  */
    internal abstract inner class Traverser : Iterator<Node<K, V>> {
        val expectedNanos: Long = nanos

        var current: Node<K, V>? = null

        var next: Node<K, V>? = null

        override fun hasNext(): Boolean {
            if (nanos != expectedNanos) {
                throw ConcurrentModificationException()
            } else if (next != null) {
                return true
            } else if (this.isDone) {
                return false
            }
            next = computeNext()
            return (next != null)
        }

        override fun next(): Node<K, V> {
            if (!hasNext()) {
                throw NoSuchElementException()
            }
            current = next
            next = null
            return current!!
        }


        fun computeNext(): Node<K, V>? {
             var node: Node<K, V>? = if (current == null) sentinel() else current
            while (true) {
                node = traverse(node!!)
                if (node !== sentinel()) {
                    return node
                } else if ((goToNextBucket().also { node = it }) != null) {
                    continue
                } else if ((goToNextWheel().also { node = it }) != null) {
                    continue
                }
                return null
            }
        }

        /** Returns if the iteration has completed.  */
        abstract val isDone: Boolean

        /** Returns the sentinel at the current wheel and bucket position.  */
        abstract fun sentinel(): Node<K, V>?

        /** Returns the node's successor, or the bucket's sentinel if at the end.  */
        abstract fun traverse(node: Node<K, V>): Node<K, V>?

        /** Returns the sentinel for the wheel's next bucket, or null if the wheel is exhausted.  */
        //@Nullable
        abstract fun goToNextBucket(): Node<K, V>?

        /** Returns the sentinel for the next wheel's bucket position, or null if no more wheels.  */
        //@Nullable
        abstract fun goToNextWheel(): Node<K, V>?
    }

    internal inner class AscendingIterator : Traverser() {
        var wheelIndex: Int = 0
        var steps: Int = 0

        override val isDone: Boolean
            get() = (wheelIndex == wheel.size)

        override fun sentinel(): Node<K, V> {
            return wheel[wheelIndex][bucketIndex()]
        }

        override fun traverse(node: Node<K, V>): Node<K, V>? {
            return node.nextInWriteOrder
        }

        //@Nullable
        override fun goToNextBucket(): Node<K, V>? {
            return if (++steps < wheel[wheelIndex].size)
                wheel[wheelIndex][bucketIndex()]
            else
                null
        }

       // @Nullable
        override fun goToNextWheel(): Node<K, V>? {
            if (++wheelIndex == wheel.size) {
                return null
            }
            steps = 0
            return wheel[wheelIndex][bucketIndex()]
        }

        fun bucketIndex(): Int {
            val ticks = (nanos ushr SHIFT[wheelIndex].toInt()).toInt()
            val bucketMask = wheel[wheelIndex].size - 1
            val bucketOffset = (ticks and bucketMask) + 1
            return (bucketOffset + steps) and bucketMask
        }
    }

    internal inner class DescendingIterator : Traverser() {
        var wheelIndex: Int = wheel.size - 1
        var steps: Int = 0

        override val isDone: Boolean
            get() = (wheelIndex == -1)

        override fun sentinel(): Node<K, V> {
            return wheel[wheelIndex][bucketIndex()]
        }

       // @Nullable
        override fun goToNextBucket(): Node<K, V>? {
            return if (++steps < wheel[wheelIndex].size)
                wheel[wheelIndex][bucketIndex()]
            else
                null
        }

        //@Nullable
        override fun goToNextWheel(): Node<K, V>? {
            if (--wheelIndex < 0) {
                return null
            }
            steps = 0
            return wheel[wheelIndex][bucketIndex()]
        }

        override fun traverse(node: Node<K, V>): Node<K, V>? {
            return node.previousInWriteOrder
        }

        fun bucketIndex(): Int {
            val ticks = (nanos ushr SHIFT[wheelIndex].toInt()).toInt()
            val bucketMask = wheel[wheelIndex].size - 1
            val bucketOffset = (ticks and bucketMask)
            return (bucketOffset - steps) and bucketMask
        }
    }

    /** A sentinel for the doubly-linked list in the bucket.  */
    class Sentinel<K, V> : Node<K, V>() {
        var prev: Node<K, V>?
        var next: Node<K, V>? = this

        init {
            prev = next
        }

        override var previousInVariableOrder: Node<K, V>? by ::prev

        override var nextInVariableOrder: Node<K, V>? by ::next

        //@get:Nullable
        override val key: K?  = null

        override val keyReference: Any?
            get() {
                throw UnsupportedOperationException()
            }

        //@get:Nullable
        override var value: V? = null

        override val valueReference: Any?
            get() {
                throw UnsupportedOperationException()
            }

         override fun setValue(value: V, referenceQueue: ReferenceQueue<V>?) {
             this.value = value
         }

        override fun containsValue(value: V): Boolean = false

        override val isAlive: Boolean
            get() = false
        override val isRetired: Boolean
            get() = false
        override val isDead: Boolean
            get() = false

        public override fun retire() {}
        public override fun die() {}
    }

    companion object {
        /*
   * A timer wheel [1] stores timer events in buckets on a circular buffer. A bucket represents a
   * coarse time span, e.g. one minute, and holds a doubly-linked list of events. The wheels are
   * structured in a hierarchy (seconds, minutes, hours, days) so that events scheduled in the
   * distant future are cascaded to lower buckets when the wheels rotate. This allows for events
   * to be added, removed, and expired in O(1) time, where expiration occurs for the entire bucket,
   * and the penalty of cascading is amortized by the rotations.
   *
   * [1] Hashed and Hierarchical Timing Wheels
   * http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
   */
        val BUCKETS: IntArray = intArrayOf(64, 64, 32, 4, 1)

        /**
         * 可以发现在元素被添加时它的过期时间已经被计算好了。
         * 接着回到 findBucket 方法，其中有逻辑 duration < SPANS[i + 1] 确定节点所在时间轮的层级。
         * SPANS 数组中存储的是层级的 “时间跨度边界”，
         * 如注释中标记的，SPANS[0] 表示第一层级的时间为 1.07s，
         * SPANS[1] 表示第二层级的时间为 1.14m，
         * for 循环开始时便以 SPANS[1] 作为比较，
         * 如果 duration 小于 SPANS[1]，那么将该节点放在第一层级，
         * 那么第一层级的时间范围为 t < 1.14 min，为秒级的时间跨度；
         * 第二层级的时间范围为 1.14 min <= t < 1.22 h，为分钟级的时间跨度，接下来的时间跨度以此类推。
         * 在这里也明白了为什么 final Node<K, V>[][] wheel 数据结构会将第一行、第二行元素大小设定为 64，
         * 因为第一行为秒级别的时间跨度，60s 即为 1min，那么在这个秒级别的跨度下 64 的容量足以，同理，
         * 第二行为分钟级别的时间跨度，60min 即为 1h，那么在这个分钟级别的跨度下 64 的容量也足够了。
         */
        val SPANS: LongArray = longArrayOf(
            ceilingPowerOfTwo(1.seconds.inWholeNanoseconds),  // 1.07s
            ceilingPowerOfTwo(1.minutes.inWholeNanoseconds),  // 1.14m
            ceilingPowerOfTwo(1.hours.inWholeNanoseconds),  // 1.22h
            ceilingPowerOfTwo(1.days.inWholeNanoseconds),  // 1.63d
            BUCKETS[3] * ceilingPowerOfTwo(1.days.inWholeNanoseconds),  // 6.5d
            BUCKETS[3] * ceilingPowerOfTwo(1.days.inWholeNanoseconds)  // 6.5d
        )

        val SHIFT: LongArray = longArrayOf(
            SPANS[0].countLeadingZeroBits().toLong(),
            SPANS[1].countLeadingZeroBits().toLong(),
            SPANS[2].countLeadingZeroBits().toLong(),
            SPANS[3].countLeadingZeroBits().toLong(),
            SPANS[4].countLeadingZeroBits().toLong()
//            numberOfTrailingZeros(SPANS[0]).toLong(),
//            numberOfTrailingZeros(SPANS[1]).toLong(),
//            numberOfTrailingZeros(SPANS[2]).toLong(),
//            numberOfTrailingZeros(SPANS[3]).toLong(),
//            numberOfTrailingZeros(SPANS[4]).toLong(),
        )
    }
}